//
// Created by Administrator on 2025/8/1.
//
#pragma once
#include <iostream>
#ifndef LIST_H
#define LIST_H

namespace single_list {
    template<class T>
    struct Node {
        explicit Node(const T &t = T()): data(t), _next(nullptr) {
        }

        T data;
        Node<T> *_next;
    };

    template<class T>
    class list {
    public:
        /**
         * 创建一个迭代器
         */
        class iterator {
        public:
            explicit iterator(Node<T> *ptr = nullptr): _ptr(ptr) {
            }

            bool operator!=(const iterator &it) {
                return _ptr != it._ptr;
            }

            void operator++() {
                _ptr = _ptr->_next;
            }

            T &operator*() {
                return (*_ptr).data;
            }

            const T &operator*() const {
                return *_ptr.data;
            }

        private:
            Node<T> *_ptr;
        };

        /**
         * 返回迭代器
         */

        iterator begin() {
            return iterator(_head->_next);
        }

        iterator end() {
            return iterator(nullptr);
        }

        /**
         * 构造函数
         */
        list(): _size(0) {
            _head = new Node<T>;
        }

        ~list() {
            Node<T> *cur = _head;
            while (cur != nullptr) {
                Node<T> *next = cur->_next;
                delete cur;
                cur = next;
            }
        }

        /**
         *
         * @param t 插入一个数据
         */
        void insertNode(const T &t) {
            Node<T> *cur = _head;
            while (cur->_next != nullptr) {
                cur = cur->_next;
            }
            cur->_next = new Node<T>(t);
        }

        /**
         *
         * @param t 在头部插入一个数据
         */
        void headInsertNode(const T &t) {
            Node<T> *cur = _head->_next;
            auto *newNode = new Node<T>(t);
            _head->_next = newNode;
            newNode->_next = cur;
        }

        /**
         *
         * @param t 查询的数据
         * @return 返回找到的节点
         */
        Node<T> *selectNode(const T &t) {
            Node<T> *cur = _head->_next;
            while (cur != nullptr) {
                if (cur->data == t) {
                    return cur;
                } else {
                    cur = cur->_next;
                }
            }
            return nullptr;
        }

        /**
         *
         * @param t 删除指定的元素，只删除一个元素
         */
        void deleteNode(const T &t) {
            Node<T> *cur = _head->_next;
            Node<T> *pre = _head;
            while (cur != nullptr) {
                if (cur->data == t) {
                    pre->_next = cur->_next;
                    delete cur;
                    cur = nullptr;
                } else {
                    pre = cur;
                    cur = cur->_next;
                }
            }
        }

        /**
         *
         * @param t 删除所有的t
         */
        void deleteAllNode(const T &t) {
            Node<T> *cur = _head->_next;
            Node<T> *pre = _head;
            while (cur != nullptr) {
                if (cur->data == t) {
                    pre->_next = cur->_next;
                    delete cur;
                    cur = pre->_next;
                } else {
                    pre = cur;
                    cur = cur->_next;
                }
            }
        }

        // 显示链表中的所有元素
        void show() {
            Node<T> *cur = _head->_next; // 从头结点的下一个节点开始遍历
            while (cur != nullptr) {
                // 如果当前节点不为空
                std::cout << cur->data << "  "; // 输出当前节点的数据
                cur = cur->_next; // 将当前节点指向下一个节点
            }
            std::cout << std::endl; // 输出换行符
        }

        //求链表倒数第K个节点
        friend bool selectKNode(const list &list1, const int k) {
            Node<T> *cur = list1._head;
            Node<T> *pre = list1._head;
            for (int m = 0; m < k; ++m) {
                cur = cur->_next;
                if (cur == nullptr) {
                    return false;
                }
            }
            while (cur != nullptr) {
                cur = cur->_next;
                pre = pre->_next;
            }
            if (pre != nullptr)
                std::cout << pre->data << std::endl;
            return true;
        }

        //这一个是友元函数，这个是参数必须是具化的，不然编译器是编不过的
        friend void showNumber(const list<int> &list1);

        friend void mergeTwoList(const list<int> &list1, const list<int> &list2);

        //逆序整个链表
        friend void reverseList(list &list) {
            Node<T> *first = list._head->_next;
            Node<T> *second = first->_next;
            first->_next = nullptr;
            while (second != nullptr) {
                Node<T> *temp = second->_next;
                list._head->_next = second;
                second->_next = first;
                first = second;
                second = temp;
            }
        } ;
        //链表是不是存在环，环的出口是哪个
        friend bool isExistCircle(const Node<int> *head);
        //删除倒数第K个节点
        friend void deleteKNode(const list<int> &list, int k);
        //旋转链表（这个题的意思是右移N个节点，尾部的节点变头部的节点，例如 1->2->3->4 右移2个节点变成 3->4->1->2）
        static void rotateList(const list<int> &list, const int k) {
            Node<int>* cur = list._head->_next;
            //假如只有一个节点的话，不改变链表
            if (cur == nullptr || cur->_next == nullptr) {
                return;
            }
            int length = 0;
            //如果不为空，先计算这个链表的长度
            while (cur!=nullptr) {
                cur = cur->_next;
                length++;
            }
            //计算需要移动的步数
            int step  = k % length;
            //如果步数是0的话，不改变链表
            if (step == 0) {
                return;
            }
            //如果步数不是0的话，开始移动
            step  = length - step;
            //开始移动
            cur = list._head->_next;
            Node<int>* pre = list._head;
            Node<int>* first = list._head->_next;
            for (int i = 0 ;i < step ;i++) {
                cur = cur->_next;
            }
            //找到cur上一个节点
            while (pre->_next!=cur) {
                pre = pre->_next;
            }
            //开始移动
            list._head->_next = cur;
            pre->_next = nullptr;
            //找到最后一个节点
            while (cur->_next!=nullptr) {
                cur = cur ->_next;
            }
            cur->_next = first;

        }
    private:
        Node<T> *_head;
        int _size;
    };


    // 合并两个有序链表
    inline void mergeTwoList(const list<int> &list1, const list<int> &list2) {
        // 获取链表1的头节点
        Node<int> *head = list1._head->_next;
        // 获取链表2的头节点
        Node<int> *s_head = list2._head->_next;
        // 获取链表1的尾节点
        Node<int> *last = list1._head;
        // 将链表2的头节点置为空
        list2._head->_next = nullptr;
        // 遍历链表1和链表2，将较小的节点连接到链表1的尾节点
        while (s_head != nullptr && head != nullptr) {
            if (head->data > s_head->data) {
                // 将链表2的节点连接到链表1的尾节点
                last->_next = s_head;
                // 移动链表2的头节点
                s_head = s_head->_next;
                // 将链表1的尾节点指向链表2的头节点
                // last->_next->_next=head;
                // 移动链表1的尾节点
                last = last->_next;
            } else {
                // 将链表1的节点连接到链表1的尾节点
                last->_next = head;
                // 移动链表1的尾节点
                last = last->_next;
                // 移动链表1的头节点
                head = head->_next;
            }
        }
        // 如果链表1已经遍历完，将链表2的剩余节点连接到链表1的尾节点
        if (head == nullptr) {
            last->_next = s_head;
        }
        // 如果链表2已经遍历完，将链表1的剩余节点连接到链表1的尾节点
        if (s_head == nullptr) {
            last->_next = head;
        }
    }

    //链表中是不是有环，求环入口点
    inline bool isExistCircle(const Node<int> *head) {
        const Node<int> *fast = head;
        const Node<int> *slow = head;
        while (fast != nullptr && fast->_next != nullptr) {
            fast = fast->_next->_next;
            slow = slow->_next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast->_next;
                    slow = slow->_next;
                }
                std::cout << "环入口点为：" << fast->data << std::endl;
                //找到了环
                return true;
            }
        }
        return false;
    }

    //判断链表是不是相交（两个链表在某个节点处以后的数据相同）
    inline bool isIntersect(const Node<int> *n1, const Node<int> *n2) {
        int cn1 = 0;
        int cn2 = 0;
        const Node<int> *cur1 = n1;
        const Node<int> *cur2 = n2;
        while (cur1 != nullptr) {
            cur1 = cur1->_next;
            ++cn1;
        }
        while (cur2 != nullptr) {
            cur2 = cur2->_next;
            ++cn2;
        }
        cur1 = n1;
        cur2 = n2;
        if (cn1 > cn2) {
            int offset = cn1 - cn2;
            while (offset--) {
                cur1 = cur1->_next;
            }

            while (cur1 != nullptr && cur2 != nullptr) {
                if (cur1 == cur2) {
                    std::cout << "两个链表相交的点：" << cur1->data << std::endl;
                    return true;
                }
                cur1 = cur1->_next;
                cur2 = cur2->_next;
            }
        } else {
            int offset = cn2 - cn1;
            while (offset--) {
                cur2 = cur2->_next;
            }
            while (cur2 != nullptr && cur1 != nullptr) {
                if (cur2 == cur1) {
                    std::cout << "两个链表相交的点:" << cur2->data << std::endl;
                    return true;
                }
                cur2 = cur2->_next;
                cur1 = cur1->_next;
            }
        }
        return false;
    } ;
    //删除倒数第k个节点
    inline void deleteKNode(const list<int> &list, int k) {
        Node<int> *pre = list._head;
        Node<int> *cur = list._head;
        k = k + 1;
        while (k--) {
            if (cur!=nullptr)
                cur = cur->_next;
            if (cur == nullptr && k>0) {
                std::cout << "链表长度小于k" << std::endl;
                return;
            }
        }
        while (cur != nullptr) {
            cur = cur->_next;
            pre = pre->_next;
        }
        const Node<int> *deleteNode = pre->_next;
        if (deleteNode != nullptr) {
            pre->_next = deleteNode->_next;
            delete deleteNode;
            deleteNode = nullptr;
        }
    }
}
#endif //LIST_H
